package com.lazycat.leetcode.editor.cn;
//2023-07-22 12:22:19
//给定两条线段（表示为起点start = {X1, Y1}和终点end = {X2, Y2}），如果它们有交点，请计算其交点，没有交点则返回空值。 
//
// 要求浮点型误差不超过10^-6。若有多个交点（线段重叠）则返回 X 值最小的点，X 坐标相同则返回 Y 值最小的点。 
//
// 
//
// 示例 1： 
//
// 输入：
//line1 = {0, 0}, {1, 0}
//line2 = {1, 1}, {0, -1}
//输出： {0.5, 0}
// 
//
// 示例 2： 
//
// 输入：
//line1 = {0, 0}, {3, 3}
//line2 = {1, 1}, {2, 2}
//输出： {1, 1}
// 
//
// 示例 3： 
//
// 输入：
//line1 = {0, 0}, {1, 1}
//line2 = {1, 0}, {2, 1}
//输出： {}，两条线段没有交点
// 
//
// 
//
// 提示： 
//
// 
// 坐标绝对值不会超过 2^7 
// 输入的坐标均是有效的二维坐标 
// 
//
// Related Topics 几何 数学 👍 84 👎 0

import exam.mian01.Main;

class IntersectionLcci {
    public static void main(String[] args) {
        //创建该题目的对象方便调用
        Solution solution = new IntersectionLcci().new Solution();
    }
    //leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    private double[] ans = new double[0];
    public double[] intersection(int[] start1, int[] end1, int[] start2, int[] end2) {
        //将数字中点的坐标取出
        int x1 = start1[0],y1 = start1[1];
        int x2 = end1[0],y2 = end1[1];
        int x3 = start2[0],y3 = start2[1];
        int x4 = end2[0],y4 = end2[1];

        //判断是否平行
        if((y4-y3)*(x2-x1) == (y2-y1)*(x4-x3)){
            //若平行，则判断（x3，y3）是否在直线 （x1，y1）～（x2，y2）
            if((y2-y1)*(x3-x1) == (y3-y1)*(x2-x1)){

                if(inside(x1,y1,x2,y2,x3,y3)){
                    update(x3,y3);
                }

                if(inside(x1,y1,x2,y2,x4,y4)){
                    update(x4,y4);
                }

                if(inside(x3,y3,x4,y4,x1,y1)){
                    update(x1,y1);
                }

                if(inside(x3,y3,x4,y4,x2,y2)){
                    update(x2,y2);
                }
            }
        }else {
            //联立方程得到t1和t2的值
            double t1 = (double) (x3*(y4-y3)+y1*(x4-x3)-y3*(x4-x3)-x1*(y4-y3)) / ((x2-x1)*(y4-y3) - (x4-x3)*(y2-y1));
            double t2 = (double) (x1*(y2-y1)+y3*(x2-x1)-y1*(x2-x1)-x3*(y2-y1)) / ((x4-x3)*(y2-y1) - (x2-x1)*(y4-y3));

            if(t1 >= 0.0 && t1<=1.0 && t2>=0.0 && t2<=1.0){
                ans = new double[]{x1+t1*(x2-x1),y1+t1*(y2-y1)};
            }
        }
        return ans;
    }

    private boolean inside(int x1,int y1,int x2,int y2,int xn,int yn){
        return  (x1 == x2 || (Math.min(x1,x2)<= xn && xn<= Math.max(x1,x2))) &&
                (y1 == y2 || (Math.min(y1,y2) <= yn && yn <= Math.max(y1,y2)));
    }

    private void update(double xn,double yn){
        if(ans.length==0 || xn < ans[0] || (xn == ans[0] & yn < ans[1])){
            ans = new double[]{xn,yn};
        }
    }
}
//leetcode submit region end(Prohibit modification and deletion)

}